package algorithm.datastructure.nn;


import java.util.LinkedList;
import java.util.List;
import java.util.Random;

/**
 * https://www.ryanligod.com/2018/11/29/2018-11-29%20HNSW%20%E4%B8%BB%E8%A6%81%E7%AE%97%E6%B3%95/
 *
 * https://github.com/nmslib/hnswlib
 *
 * https://www.cxyzjd.com/article/lijinwen920523/116093606
 *
 */


// TODO
public class HNSW {

    static class Vertex {
        int id;  // 节点自增唯一主键id
        int neighborsInThisLayer; // 在当前层的邻居的数量
        // int flag;
        // int reserved;
        List<Vertex> neighbors;
        String data;
        double[] vector;
    }

    int size;
    int totalLayer;
    Random rand = new Random();

    // ground(第0层)存储节点的数据以及第0层的邻居关系，每个节点的数据主要包括：邻居的数量(size)，flag，保留的一个字节，邻居节点的id，
    // 自己的data数据，以及一个id(插入节点时可指定的一个代号)。
    List<Vertex> ground;

    // lists是一个二维数组，其中的每一行代表一个节点从第1层到maxLevel层每一层的邻居关系。每个节点每一层的数据结构主要包括：邻居的数量(size)，
    // 保留的两个字节，以及该层的邻居的id。
    List<List<Vertex>> lists;


    // 添加节点
    // 添加节点时，先检查一下该节点的label是否已经存在了，如果存在的话，直接更新节点，下一节会详细介绍。如果不存在，则直接添加节点。主要步骤为：
    // 1. 节点id自增加1
    // 2. 随机初始化层数 curlevel
    // 3. 初始化节点相关数据结构，主要包括：将节点数据以及label拷贝到第0层数据结构(data_level0_memory_)中；
    //    为该节点分配存储0层以上的邻居关系的结构，并将其地址存储在linkLists_中
    // 4. 如果这是第一个元素，只需将该节点作为HNSW的entrypoint，并将该元素的层数作为当前的最大层。
    // 5. 如果不是第一个元素：
    //    1）那么从当前图的从最高层逐层往下寻找直至节点的层数+1停止，寻找到离data_point最近的节点，作为下面一层寻找的起始点。
    //    2）从curlevel依次开始往下，每一层寻找离data_point最接近的ef_construction_（构建HNSW是可指定）个节点构成候选集，
    //       再从候选集中选择M个节点与data_point相互连接。至于如何寻找ef_construction_个候选节点，在后文搜索节点一节中解释。
    public void insert(Vertex v) {
        boolean isInG = false;
        for (Vertex vInG : ground) {
            if (vInG.id == v.id) {isInG = true; break;}
        }

        if (isInG) {
            update(v);
        } else {
            v.id = size++;
            int curlevel = rand.nextInt(totalLayer);
            ground.add(v);
        }


    }


    // 更新节点
    // 插入节点时，如果节点的label已经存在了，那么直接更新节点。更新节点主要分为三步：
    // 1. 更新节点的数据；
    // 2. 从0层逐层往上，直至该节点的最高层，在每一层取待更新节点的部分邻居，更新它们的邻居；
    // 3. 从上往下依次更新待更新节点的邻居。
    public void update(Vertex v) {

    }

    // 搜索节点
    public List<Vertex> search(Vertex v, int n) {
        return new LinkedList<>();
    }

}
